package butines.common.graph;

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class PathFinderAStar/* implements PathFinder */{
/*
	private Graph graph;
	private Heuristic heuristic;
	private Node source;
	private Node target;
	private boolean found;
	private List<Node> path;

	private AStarNode openList;
	private AStarNode closeList;
	private AStarNode current;

	public PathFinderAStar(Graph graph, Heuristic heuristic) {
		this.graph = graph;
		this.heuristic = heuristic;
	}

	public void search(int iSource, int iTarget) {
		openList = null;
		closeList = null;
		
		path = new LinkedList<Node>();
		found = false;
		
		source = graph.getNode(iSource);
		target = graph.getNode(iTarget);
		
		current = new AStarNode();
		current.node = source;
		current.parent = current;
		
		addOpenList(current);
	}

	private void createPath() {
		Node node = target;
		path.add(node);
		while (node != source) {
			AStarNode parent = wrappers[node.getId()].parent;
			node = parent.node;
			path.add(node);
		}
	}

	private AStarNode nextOpenList() {
		AStarNode temp = openList;
		openList = openList.next;
		return temp;
	}
	
	private AStarNode getOpenList(Node node) {
		AStarNode curr = openList;
		while (curr != null && curr.node != node) {
			curr = curr.next;
		}
		return (curr != null && curr.node == node) ? curr : null ;
	}
	
	private void addOpenList(AStarNode node) {
		
		AStarNode prev = null;
		AStarNode curr = openList;
		
		while (curr != null && node.fCost > curr.fCost) {
			prev = curr;
			curr = curr.next;
		}
		
		node.next = curr;
		if (prev == null) {
			openList = node;
		} else {
			prev.next = node;
		}
		
	}
	
	private void sortOpenList(AStarNode node) {
		AStarNode prev = null;
		AStarNode curr = openList;
		
		while (curr != null && node.fCost > curr.fCost) {
			prev = curr;
			curr = curr.next;
		}
		
	}
	
	private boolean existsCloseList(Node node) {
		AStarNode curr = closeList;
		while (curr != null && curr.node != node) {
			curr = curr.next;
		}
		return (curr != null && curr.node == node);
	}
	
	public void next() {
		current = nextOpenList();
		
		if (closeList == null) {
			closeList = current;
		} else {
			closeList.next = current;
		}
		
		if (current.node == target) {
			createPath();
			found = true;
			return;
		}

		for (Edge edge : current.node.getEdges()) {
			Node nodeTo = edge.getTo();
			if (existsCloseList(nodeTo)) {
				continue;
			}

			double hCost = heuristic.calcule(nodeTo, target);
			double gCost = current.gCost + edge.getCost();
			
			AStarNode wrapper = getOpenList(nodeTo);
			if (wrapper == null) {
				wrapper = new AStarNode();
				wrapper.parent = current;
				wrapper.node = nodeTo;
				wrapper.fCost = gCost + hCost;
				wrapper.gCost = gCost;
				wrapper.hCost = hCost;
				addOpenList(wrapper);
			} else if (wrapper.gCost > gCost) {
				wrapper.parent = current;
				wrapper.fCost = gCost + hCost;
				wrapper.gCost = gCost;
				sortOpenList(wrapper);
			}
			
		}
	}

	public boolean hasNext() {
		return !openList.isEmpty() && !found;
	}

	public boolean isFound() {
		return found;
	}

	public List<Node> getPath() {
		return path;
	}
	
	public Node getSource() {
		return source;
	}

	public Node getTarget() {
		return target;
	}
	
	public Node getCurrent() {
		return current == null ? null : current.node;
	}


//	private Comparator<AStarNode> ORDER_COST = new Comparator<AStarNode>() {
//		public int compare(AStarNode a, AStarNode b) {
//			double value = a.fCost - b.fCost;
//			if (value > 0) {
//				return 1;
//			}
//			if (value < 0) {
//				return -1;
//			}
//			return 0;
//		}
//	};  
//	
//	private Comparator<AStarNode> ORDER_ID = new Comparator<AStarNode>() {
//		public int compare(AStarNode a, AStarNode b) {
//			return a.node.compareTo(b.node);
//		}
//	};
	
	class AStarNode {
		AStarNode parent, next;
		Node node;
		
		double gCost;
		double fCost;
		double hCost;
		
	}
	*/
}
